Quantum weirdness in query-to-communication simulation and the role of symmetry

Abstract

Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function $f : {0,1}^n \to {0,1}$ and $G \in {AND_2, XOR_2}$, the bounded-error quantum communication complexity of the composed function (f \circ G) equals O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is known as the BCW Simulation Theorem. This is in contrast with the classical setting, where it is easy to show that $R^{cc}(f \circ G) \leq 2R(f)$, where R^{cc} and R denote bounded-error communication and query complexity, respectively. We exhibited a total function for which the (log n) overhead in the BCW simulation is required.

We also answer several questions in quantum query-to-communication simulation:

1. We show that the (log n) overhead is not required when f is symmetric (i.e., depends only on the Hamming weight of its input), generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05).

2. In order to prove the above, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function.

3. One may ask whether the (log n) overhead in the BCW Simulation Theorem can be avoided even when f is transitive, which is a weaker notion of symmetry. We give a strong negative answer by showing that the (log n) overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2 (this corresponds to the unbounded-error model of communication).

4. We also give, among other things, a general recipe to construct functions for which the (log n) overhead is required in the BCW Simulation Theorem in the bounded-error communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.

This talk is based on two joint works with Sourav Chakraborty, Arkadev Chattopadhyay, Peter Hoyer, Nikhil Mande and Ronald de Wolf.

Video